This invention relates to the field of methods for regulating traffic in a communications network. More particularly, this invention relates to generalized processor sharing (GPS) schedulers, and specifically, to GPS schedulers which statistically multiplex heterogeneous quality of service (QoS) classes.
A communications network is one means for transmitting or carrying traffic (e.g., signals representing information such as data, voice, text, and/or video) between endpoints (e.g., host machines, fax machines, or terminals) connected to the network. The network comprises nodes connected, to each other and to the endpoints, by links. Typically, each link is bi-directional (i.e., traffic may be conveyed or transmitted in the forward and reverse directions), and each link is characterized by parameters, such as bandwidth or capacity in each direction. The nodes advantageously include buffers. If a link does not have a sufficient available bandwidth to carry traffic received at a node, a buffer in the node may be used to store the received traffic until such time as the link has a sufficient available bandwidth.
Networks are increasingly being used for the reliable, high-speed transmission of traffic between endpoints over wide areas. This increased use is bringing major changes to network services and architecture/infrastructure design. In particular, a wide spectrum of new consumer and business services, such as video-on-demand and video teleconferencing, are expected to be offered on Broadband Integrated Services Digital Networks (BISDN) as well as Internet telephony. These new services will be characterized by a wide range of traffic characteristics (e.g., bandwidth) and with different quality of service (QoS) requirements (e.g., maximum delay through the network and maximum information loss rate). The principal technique for transmission in BISDN is Asynchronous Transfer Mode (ATM). See, for example, S. E. Minzer, xe2x80x9cBroadband ISDN and Asynchronous Transfer Mode,xe2x80x9d IEEE Comm. Mag., pp. 17-24. September 1989. Other transmission techniques include Internet Protocol (IP), among others.
When traffic is to be carried in an ATM network, an initiating endpoint requests that a bi-directional path (i.e., a connection comprising nodes and links) be established in the network between the initiating endpoint and a specified destination endpoint. In an ATM network, the path that is established is a so-called xe2x80x9cvirtual circuitxe2x80x9d (VC) by which it is meant that the initiating endpoint simply specifies the destination endpoint, and the network carries the traffic from the initiating endpoint to the destination endpoint as though they are connected by a direct circuit. A VC is also referred to herein as a connection. Traffic in an ATM network is formatted into cells or packets. Note that in Internet Protocol networks, no connection is defined, but packets belonging to different flows are, however, identified.
Admission control policies govern whether the network can accommodate, for example, a request to establish a new VC. The admission decision is typically based on: (1) traffic descriptors (e.g., average bandwidth and burstiness) characterizing the traffic to be carried and (2) any quality of service requirements for the traffic. The admission decision will also be based on what resources are available in the network (e.g., the amount of unused bandwidth in the links, and the unused buffer space in nodes) to accommodate the request. A request for admission typically will specify or provide the traffic descriptors. The network will, in turn (based on the specified traffic descriptors), determine the amount of network resources that will need to be assigned to the request. Based on the determination, the network will decide whether to admit the request. If the request is admitted, a xe2x80x9ccontractxe2x80x9d is made by which the network agrees to carry the traffic and to meet any quality of service guarantees so long as the traffic stays within the specified traffic descriptors. The performance of ATM or IP networks depends on admitted connections complying with their contracts. For example, congestion may be caused by an endpoint supplying information to the network so as to exceed contract specifications, thereby causing statistical fluctuations in the traffic flow through the network. Such fluctuations can degrade network performance and affect quality of service levels for other connections in the network. Accordingly, a network typically monitors, or controls traffic on, connections to ensure that the connections comply with their contracts.
Various techniques have been proposed to monitor and control traffic on networks, as well the allocated resources. Generalized Processor Sharing (GPS) provides the basis for the packet scheduler of choice in Internet Protocol (IP) routers and ATM switches of the future. See, e.g., S. Keshav, An Engineering Approach to Computer Networking, Addison-Wesley, Reading, Mass., 1997; G. Kesidis, ATM Network Performance, Kluwer, Boston, Mass., 1996; D. Stiliadis and A. Varma, xe2x80x9cRate-proportional servers: A design methodology for fair queueing algorithmsxe2x80x9d, IEEE/ACM Trans. Networking 6, April 1998, pp. 164-74; and D. Stiliadis and A. Varma, xe2x80x9cEfficient fair queueing algorithms for packet-switched networksxe2x80x9d, IEEE/ACM Trans. Networking 6, April 1998, pp. 175-85. A GPS scheduler defines how cells are serviced out of the buffer of a connection and sent over the link with a specified total link bandwidth.
The currently accepted approach for the design of the GPS scheduler and the control of networks which use it is based on deterministic QoS guarantees. In this connection, the work and bounds of Parekh and Gallager form an important and original point of reference. See, e.g., A. K. Parekh, xe2x80x9cA generalized processor sharing approach to flow control in integrated services networkxe2x80x9d, Ph.D. dissertation, LIDS-TH-2089, MIT, February 1992; A. K. Parekh and R. G. Gallager, xe2x80x9cA generalized processor sharing approach to flow controlxe2x80x94The single node casexe2x80x9d, IEEE/ACM Trans. Networking 1, June 1993, pp. 344-57; and Parekh et al. and R. G. Gallager, xe2x80x9cA generalized processor sharing approach to flow control in integrated services networkxe2x80x94The multiple node casexe2x80x9d, IEEE/ACM Trans. Networking, April 1994, pp. 137-50. However, it is generally accepted that the deterministic bounds using lossless multiplexing are overly conservative, thus limiting capacity and the utility of the approach to guide the design and operations of real networks.
To address the limitations of deterministic QoS guarantees, this invention develops a framework for GPS scheduling and network control which is based on statistical QoS guarantees and statistical multiplexing. We give the design of GPS weights which maximize coverage of operating points in the number of connections of heterogeneous QoS classes with only a very small repertoire of weights, together with the associated design of connection admission control (CAC). The gain in capacity is then typically significant.
The description and results presented here are in the framework of end-to-end QoS guarantees, but could be used in the context of any scheduling problem requiring QoS guarantees, including IP networks. We consider two heterogeneous QoS classes coexisting with a third, best effort class. These three classes are sometimes referred to in the industry as gold, silver and bronze QoS guarantees. The QoS classes have a specified end-to-end delay requirement together with a bound, typically quite small, on the probability of its violation, or loss. The role of the best effort traffic is important in our conceptual framework, and a high level objective is to maximize the bandwidth available to best effort traffic while just satisfying the guarantees of the QoS classes.
The main contributions of this invention are for a single node in which the service discipline is GPS. The procedure applies to each node on the end-to-end path, provided peak-rate regulation is carried out as described below, and provided an appropriate characterization, described below, is given of the traffic to each node.
There are K=(K1, K2) connections or sources of the two QoS classes, and each connection""s scheduling parameters are xcfx86j and Po(j), for class j connections, where the weight xcfx86j, in relation to the weights of the other connections, determines the connection""s share of the bandwidth, which, however, is not allowed to exceed the peak rate Po(j). Our analysis for the single node is carried out first with peak rate regulation absent, and this analysis is then used to select Po(.) such that the analysis still holds when peak rate regulation is operative. The QoS parameters for class j are Dj, the delay bound, and Lj, the loss probability. The class dependence is important, for in one representative example, class 1 is voice-like for which D1 is small and L1 large, while class 2 is premium data-like for which D2 is large and L2 small.
The source model is the fluid rate process which is adversarial while compliant with dual leaky bucket (r,BT,P) regulation, where r and P are the mean and peak rate constraints, respectively, and BT is the token buffer size. This is an on-off process, which we call the extremal regulated source process, that transmits at peak rate from the instant that the token buffer is full till it is empty, and then turns off and remains so till the token buffer is full.
The development of the single node analysis is in two phases, lossless multiplexing followed by statistical multiplexing. The former assumes that sources may collude and in this case the above on-off process is shown to be maximally adversarial. This phase parallels the standard analysis for deterministic guarantees, except for the additional element of the delay constraint. The analysis in the latter phase combines (i) the assumption of non-colluding sources, which gives statistical independence to the sources and uniformly distributed random phases to the individual sources"" rate processes, and (ii) the use of the unutilized portions of the allocated resources to sources, which is not exploited in lossless multiplexing.
The GPS weights (xcfx861, xcfx862) or, more specifically, the ratio xcfx86xcfx861/xcfx862 (which we shall also refer to as a weight) are chosen as follows. The first step is to determine the admissible set (xcfx86), i.e., for fixed xcfx86, the set of all (K1, K2) such that the statistical QoS of each connection is satisfied. The size and shape of the admissible region depends strongly on the weight. It is easy to mismatch the GPS weight to the traffic and QoS parameters of the classes. For instance, if xcfx86 is excessively large then the admissible set is limited by the QoS considerations of the class 2 connections and is consequently small in size, with the relatively few class 1 connections receiving QoS in excess of their requirements. When the weight is not properly designed resources are misallocated and sharing is inhibited.
An important concept for GPS design is the realizable set . This is the set of all (K1, K2) which are contained in the admissible set of some weight xcfx86. That is, the realizable set is the union of the admissible set (xcfx86) over all xcfx86. The role of the realizable set is as follows: say exogeneous (traffic and market) conditions dictate a desirable operating neighborhood in connections around the point (K1, K2). If this neighborhood is contained in  then an inverse problem is solved to obtain the appropriate weight. As the exogeneous conditions change, typically on a slow time scale, the GPS weight changes too in correspondence. Now, on the face of it, this notion is only of theoretical value with possibly little practical relevance, since the realization of all of  may in principle require switching between a large, even possibly an uncountable, number of weights. One of the main contributions of this invention is to show by a pragmatic design approach that most of  may be realized by either one or two weights. These are called critical weights, xcfx86c(1) and xcfx86c(2), and simple procedures for their calculations are given in this disclosure.
Next, we must determine whether one or two critical weights are needed. We classify the entire system, as characterized by the traffic and QoS parameters of both classes, to be either xe2x80x9cEffectively Homogeneousxe2x80x9d or xe2x80x9cEffectively Non-Homogeneousxe2x80x9d, depending upon whether xcfx86c(1)xe2x89xa6xcfx86c(2) or otherwise. The former is the benign case and the mid-point between the critical weights is a suitable choice to realize almost all of . In the latter case, realizing  requires switching between the critical weights, which, as argued above, would occur on a slow time scale to track exogeneous traffic conditions. In particular, switching at this rate would be compatible with the tacit assumption in the analysis that steady state exists. In our numerical investigations we have encountered examples of effectively homogeneous systems in which there exists considerable disparity in traffic and QoS parameters between the classes.
Our numerical investigations consider a wide range of traffic and QoS parameters. The results reported here for the single node provide support for our pragmatic approach to the design problem, which is based on piece-wise linear approximations to the boundaries of the admissible and realizable regions, and, more specifically, for our claim that either one or two weights suffice to realize most of . Finally, these results show that there are substantial capacity gains from statistical over deterministic, or lossless, QoS guarantees.
Proceeding to the network-wide context, the objective is to maximize carried best-effort traffic, while meeting the requirements of the QoS classes. This is the prime motivation for regulation of the peak rate of the output of the GPS schedulers. Output regulated GPS has the effect of allocating resources to the admitted QoS connections to just meet their requirements. There are further choices to be made regarding the delay budget, i.e., allocation of portions of the end-to-end delay to nodes in the path of the connection. An attractive option is to allocate the entire delay budget to the first node in the path. In the GPS framework one attraction, among others, of this invention is that the complexity of the GPS design is contained and the detailed analysis given here applies. Otherwise there is a proliferation of classes for which the GPS design problem is complexified, even though the basic framework of a single GPS node analysis of this invention remains intact.